package J.算法.动态规划;

public class _416分割等和子集 {

    public boolean canPartition(int[] nums) {
        int sum=0;
        for (int num:nums){
            sum+= num;
        }

        if (sum % 2 != 0){
            return false;
        }

        boolean[][] dp = new boolean[nums.length+1][sum/2+1];
        for (int i=0;i< nums.length;i++ ){
            dp[i][0] = true;
        }
        for (int i = 0; i < sum/2; i++) {
            dp[0][i] = false;
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (j - nums[i-1] <0){
                    dp[i][j] = dp[i - 1][j];
                }else {
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[nums.length][sum/2];

    }

}
